package leetcode.tree_problem;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 55 - II. 平衡二叉树【记忆化搜索】
 * https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
 */
public class IsBalancedFunTwo {
    //定义节点和为树的高度
    Map<TreeNode , Integer> map = new HashMap<>();
    public boolean isBalanced(TreeNode root) {

        //边界
        if (root == null)
            return true;
        //高度定义
        int left = 0;
        int right = 0;

        if (map.containsKey(root.left)){
            left = map.get(root.left);
        }else {
            left = height(root.left);
            map.put(root.left , left);
        }

        if (map.containsKey(root.right)){
            right = map.get(root.right);
        }else {
            right = height(root.right);
            map.put(root.right , right);
        }

        if(Math.abs(left - right) > 1){//判断左右树是否高度差小于一以证明平衡
            return false;
        }

        return isBalanced(root.left) && isBalanced(root.right);


    }
    public int height(TreeNode root){
        if (root == null)
            return 0;
        return 1 + Math.max(height(root.left) , height(root.right));
    }
}
